package ljl.alg.wangzheng_camp.round1.slidingwindow;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 之前做过几次
 * 我知道先记录 t 的一个 mapping，然后搞个 s 的 mappping，记录 s 里的东西
 * 如果 s 覆盖了 t，就找到了一个串，记录 start，len，
 * 再继续找，如果又找到一个，比较 len 大小，如果新的更小，就记录新的 start，len
 *
 * 一年多了吧？还不会做，呵呵
 *
 * */
public class _76_min_win {
    
    /*
    * 不会做 看答案了
    * */
    class cantdo {
        public String minWindow(String s, String t) {
            int m = s.length(), n = t.length();
            if (m < n) return "";
            Map<Character, Integer> tMap = new HashMap<>();
            Map<Character, Integer> sMap = new HashMap<>();
            LinkedList<Integer> indexes = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
                char c = s.charAt(i);
                sMap.put(c, sMap.getOrDefault(c, 0) + 1);
                indexes.offer(i);
            }
            for (int i = n; i < m; i++) {
                char c = s.charAt(i);
                sMap.put(c, sMap.getOrDefault(c, 0) + 1);
                indexes.offer(i);
            
            }
            return null;
        }
    }
    
    class ans {
        Map<Character, Integer> ori = new HashMap<Character, Integer>();
        Map<Character, Integer> cnt = new HashMap<Character, Integer>();
        public String minWindow(String s, String t) {
            int n = t.length();
            for (int i = 0; i < n; i++) {
                char c = t.charAt(i);
                ori.put(c, ori.getOrDefault(c, 0) + 1);
            }
            int l = 0, r = 0;
            int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
            int m = s.length();
            while (r < m) {
                if (ori.containsKey(s.charAt(r))) {
                    cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
                }
                while (check() && l <= r) {
                    if (r - l + 1 < len) {
                        len = r - l + 1;
                        ansL = l;
                        ansR = l + len;
                    }
                    if (ori.containsKey(s.charAt(l))) {
                        cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                    }
                    ++l;
                }
                r++;
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }
        public boolean check() {
            for (Map.Entry<Character, Integer> each : ori.entrySet())
                if (cnt.getOrDefault(each.getKey(), 0) < each.getValue()) return false;
            return true;
        }
    }
    
    public String minWindow(String s, String t) {
        int m = s.length(), n = t.length();
        Map<Character, Integer> dic = new HashMap<>();
        for (char c : t.toCharArray()) {
            dic.put(c, dic.getOrDefault(c, 0) + 1);
        }
        int len = Integer.MAX_VALUE, from = 0;
        int left = 0;
        Map<Character, Integer> count = new HashMap<>();
        for (int i = 0; i < m; i++) {
            char c = s.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);
            while (contains(count, dic) && left <= i) {
                int nLen;
                if ((nLen = i - left + 1) < len) {
                    len = nLen;
                    from = left;
                }
                count.put(s.charAt(left), count.getOrDefault(s.charAt(left), 0) - 1);
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(from, from + len);
    }
    boolean contains(Map<Character, Integer> count, Map<Character, Integer> dic) {
        for (Map.Entry<Character, Integer> each : dic.entrySet()) {
            if (count.getOrDefault(each.getKey(), 0) < each.getValue()) return false;
        }
        return true;
    }
    
    
}
